package leetcode
/*
 * @lc app=leetcode.cn id=839 lang=golang
 *
 * [839] 相似字符串组
 */

// @lc code=start
func isSimilar(s, t string) bool {
	diff := 0
	for i := range s {
		if s[i] != t[i] {
			diff++
		}
		if diff > 2 {return false}
	}
	return true
}

func numSimilarGroups(strs []string) int {
	n := len(strs)
	uf := newUnionFind(n)
	for i := 0; i < n; i++ {
		for j := i+1; j < n; j++ {
			if s, t:= strs[i], strs[j]; !uf.isSameRoot(i, j) && isSimilar(s, t) {
				uf.unite(i, j)
			}
		}
	}
	return uf.numRoot
}
// @lc code=end

